package com.nowcoder.Offer.BackTrack;

import org.junit.Test;

import java.util.*;

/**
 * 打印字典序
 * 例如输入字符串abc,则打印出由字符a,b,c
 * 所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 */
public class PrintDictionary {


    private ArrayList<String> ans = new ArrayList<>();

    public ArrayList<String> Permutation(String str) {
        if(str.length() == 0)
            return ans;
        backTrack(str.toCharArray(),0);
        Collections.sort(ans);
        return ans;
    }

    public void backTrack(char[] chars, int i){
        if(i == chars.length-1){
            String str = new String(chars);
            if(!ans.contains(str)){
                ans.add(str);
                return;
            }
        }
        else{

            for(int j = i; j<chars.length ; j++){
                swap(chars,i,j);
                backTrack(chars,i+1);
                swap(chars,i,j);
            }
        }
    }

    public void swap(char[] chars , int a, int b){
        if(a!=b){
            char tmp = chars[a];
            chars[a] = chars[b];
            chars[b] = tmp;
        }
    }

    @Test
    public void test(){
        String str = "abc";
        Permutation(str).forEach(System.out::println);
    }
}
















